package leetcode.editor.cn;

/**
 * [35]搜索插入位置
 * search-insert-position
 */
//给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
// 你可以假设数组中无重复元素。
// 示例 1:
// 输入: [1,3,5,6], 5
//输出: 2
// 示例 2:
// 输入: [1,3,5,6], 2
//输出: 1
// 示例 3:
// 输入: [1,3,5,6], 7
//输出: 4
// 示例 4:
// 输入: [1,3,5,6], 0
//输出: 0
// 
// Related Topics 数组 二分查找 
// 👍 912 👎 0

public class LC035_SearchInsertPosition {
    public static void main(String[] args) {
        Solution solution = new LC035_SearchInsertPosition().new Solution();
        int result = solution.searchInsert(new int[]{1, 3, 5, 6}, 7);
        System.out.println("result = " + result);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 二分查找法
         * @param nums
         * @param target
         * @return
         */
        /*public int searchInsert(int[] nums, int target) {
            int indexOfLow = 0;
            int indexOfHigh = nums.length - 1;
            int indexOfMid = 0, mid;
            while (indexOfHigh >= indexOfLow) {
//                indexOfMid = indexOfLow + (indexOfHigh - indexOfLow) / 2;
                indexOfMid = indexOfLow + ((indexOfHigh - indexOfLow) >> 1);
                mid = nums[indexOfMid];
                if (target > mid) {
                    indexOfLow = indexOfMid + 1;
                } else if (target < mid) {
                    indexOfHigh = indexOfMid - 1;
                } else {
                    return indexOfMid;
                }
            }
            if (nums[indexOfMid] > target) {
                return indexOfMid;
            } else {
                return indexOfMid + 1;
            }
        }*/

        /**
         * 顺序查找法
         *
         * @param nums
         * @param target
         * @return
         */
        public int searchInsert(int[] nums, int target) {
            for (int i = 0; i < nums.length; i++) {
                if (target <= nums[i]) {
                    return i;
                }
            }
            return nums.length;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}